package lc.动态规划;



/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/20
 */
public class 剑指Offer42_连续子数组的最大和 {


    public int maxSubArray(int[] nums) {

        // dp[i] 存放着到i位置连续子数组的最大和
        int[] dp = new int[nums.length];

        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i < dp.length; i++) {

            dp[i] = Math.max(nums[i],nums[i] + dp[i -1]);
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }

}
